//给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 
//
// 叶子节点 是指没有子节点的节点。 
//
// 
// 
// 
//
// 示例 1： 
//
// 
//输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
//输出：[[5,4,11,2],[5,8,4,5]]
// 
//
// 示例 2： 
//
// 
//输入：root = [1,2,3], targetSum = 5
//输出：[]
// 
//
// 示例 3： 
//
// 
//输入：root = [1,2], targetSum = 0
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 树中节点总数在范围 [0, 5000] 内 
// -1000 <= Node.val <= 1000 
// -1000 <= targetSum <= 1000 
// 
// 
// 
// Related Topics 树 深度优先搜索 回溯 二叉树 👍 641 👎 0

package leetcode.editor.cn;
//leetcode submit region begin(Prohibit modification and deletion)

import java.io.IOException;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution113 implements Serializable {
    transient int b;

    private void writeObject(ObjectOutputStream o)throws IOException {
        o.defaultWriteObject();
        o.writeObject(b);
    }



    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        //如果节点为空直接返回
        if (root == null)
            return res;
        Stack<TreeNode> stackNode = new Stack<>();
        Stack<List<Integer>> stackList = new Stack<>();
        stackNode.add(root);
        List<Integer> list = new ArrayList<>();
        list.add(root.val);
        stackList.add(list);
        while (!stackNode.empty()) {
            TreeNode node = stackNode.pop();
            List<Integer> tempList = stackList.pop();
            if (node.left == null && node.right == null && node.val == sum) {
                //如果满足条件，就把路径存储到res中
                res.add(tempList);
            }

            if (node.right != null) {
                tempList.add(node.right.val);
                stackList.add(new ArrayList<>(tempList));
                node.right.val += node.val;
                stackNode.push(node.right);
                tempList.remove(tempList.size() - 1);

            }
            if (node.left != null) {
                tempList.add(node.left.val);
                stackList.add(new ArrayList<>(tempList));
                node.left.val += node.val;
                stackNode.push(node.left);
                tempList.remove(tempList.size() - 1);
            }
        }
        return res;
    }


    /**
     * 迭代 ，这段代码有问题，回溯的时候list不一定就是回溯到上一个！
     * 解决方法：节点入栈的时候把对应的路径也入栈
     */
    public List<List<Integer>> pathSum2(TreeNode root, int targetSum) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        if(root == null) return result;
        Stack<TreeNode> nodeStack = new Stack<>();
        Stack<Integer> numStack = new Stack<>();
        nodeStack.push(root);
        numStack.push(targetSum-root.val);
        while(!nodeStack.isEmpty()){
            TreeNode node = nodeStack.pop();
            Integer target = numStack.pop();
            list.add(node.val);
            if(node.left == null && node.right == null){
                if(target == 0){
                    result.add(new ArrayList<>(list));
                }
                list.remove(list.size() - 1);
//                if(target == 0){
//                    result.add(list); //这里添加的是引用，后面remove的时候这里也会跟着变化！！！！
//                }
//                list.remove(list.size()-1);
            }
            if(node.right != null){
                nodeStack.push(node.right);
                numStack.push(target - node.right.val);
            }
            if(node.left != null){
                nodeStack.push(node.left);
                numStack.push(target - node.left.val);
            }
        }
        return result;
    }

        /**
         * 递归
         */
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    public List<List<Integer>> pathSum1(TreeNode root, int targetSum) {
        if(root == null){
            return result;
        }
        backTrack(root,targetSum);
        return result;
    }

    public void backTrack(TreeNode root, int target){
        target -= root.val;
        list.add(root.val);
        if(root.left == null && root.right == null){
            if(target == 0){
                result.add(new ArrayList<>(list));
            }
            return;
        }
        if(root.left != null){
            backTrack(root.left,target);
//             target += root.val;   这里target不加加了，局部变量自动回溯
            list.remove(list.size()-1);
        }
        if(root.right != null){
            backTrack(root.right,target);
//            target += root.val;
            list.remove(list.size()-1);
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(2);
        List<List<Integer>> lists = new Solution113().pathSum(root, 3);
        System.out.println(lists);
    }
}
//leetcode submit region end(Prohibit modification and deletion)
